HackerRank The Coin Change Problem
https://www.hackerrank.com/challenges/coin-change/problem
解答
code: python
#!/bin/python3
import math
import os
import random
import re
import sys
#
# Complete the 'getWays' function below.
#
# The function is expected to return a LONG_INTEGER.
# The function accepts following parameters:
# 1. INTEGER n
# 2. LONG_INTEGER_ARRAY c
#
def getWays(n, c):
# Write your code here
dp = 0 * (n+1)
dp0 = 1
for i in range(len(c)):
for j in range(ci, n+1):
dpj += dp[j-ci]
# print(ci, dp)
# 2 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1
# 5 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 2
# 3 1, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4
# 6 1, 0, 1, 1, 1, 2, 3, 2, 4, 4, 5
return dpn
if __name__ == '__main__':
fptr = open(os.environ'OUTPUT_PATH', 'w')
first_multiple_input = input().rstrip().split()
n = int(first_multiple_input0)
m = int(first_multiple_input1)
c = list(map(int, input().rstrip().split()))
# Print the number of ways of making change for 'n' units using coins having the values given by 'c'
ways = getWays(n, c)
fptr.write(str(ways) + '\n')
fptr.close()
テーマ
#dp
メモ
https://www.youtube.com/watch?v=sCIqBTHiQAE